home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / progjour / 1990 / 05 / virt.c < prev    next >
C/C++ Source or Header  |  1990-07-25  |  18KB  |  473 lines
  1. #include <stdio.h>
  2. #include <io.h>
  3. #include <fcntl.h>      /* for Microsoft-compatible O_RDWR */
  4. #include <stdlib.h>
  5. #include <errno.h>
  6. #include <sys/types.h>
  7. #include <sys/stat.h>
  8.  
  9.  /* VIRT.C.   This file contains C workhorse functions that manipulate
  10.   * disk-based virtual memory. */
  11.  
  12. #ifdef DEBUG
  13. #define D(x) x
  14. #define ND(x)
  15. #else
  16. #define D(x)
  17. #define ND(x) x
  18. #endif
  19. #define READ  1                   /* first argument to block_io()       */
  20. #define WRITE 0                   /* "                                  */
  21. #define TNAME    "$$$$vmem.tmp"   /* name used for virtual-memory       */
  22.                                   /* file. TMP environment prefix       */
  23. #define BLK_SIZE  256             /* block size (bytes)                 */
  24. #define SIGNATURE 0x5a5a          /* Identifies vmem's as valid.        */
  25.                                   /* Stored in 15-bit unsigned.         */
  26. static char     Vname[128];       /* path name to vmem file             */
  27. static unsigned Filesize = 0;     /* size of virt mem file blocks)     */
  28. static int      Vfd      = -1;    /* File handle for Vname              */
  29. typedef struct hdr {
  30.     unsigned    nblocks;          /* Size of array in blocks.           */
  31.     unsigned    offset;           /* Offset (blocks) to block start.    */
  32.     union { struct hdr  *h;       /* Next element of freelist.          */
  33.         struct vmem *v;           /* Additional info if in use.         */
  34.     } next;
  35. } hdr;
  36. typedef struct vmem {
  37.     unsigned signature:15;        /* 0x5a5a if structure valid          */
  38.     unsigned dirty    :1;         /* true if buf modified since read    */
  39.     unsigned ele_size;            /* size of one element                */
  40.     unsigned ele_per_blk;         /* number of elements in a block      */
  41.     long     num_ele;             /* number of elements in array        */
  42.     unsigned cblock;              /* block currently in buffer          */
  43.     char     *buf;                /* Swap buffer                        */
  44. } vmem;
  45. #define PUBLIC                    /* for documentation                  */
  46. #define PRIVATE static
  47. PRIVATE hdr *Freelist = NULL;     /* Pointer to free list--circular     */
  48.                                   /* linked list, initially empty       */
  49. extern  int vopen       ( void );
  50. extern  int vclose      ( void );
  51. extern  hdr *vmalloc    (long num_ele,unsigned int ele_size);
  52. extern  int vfree       (hdr *p);
  53. extern  void *vread     (hdr *p,long index);
  54. extern  void *vwrite    (hdr *p,long index,char *this);
  55. extern  long vele       (hdr *p);
  56. static  hdr *new_hdr     (unsigned nblocks, unsigned offset);
  57. static  unsigned enlarge (unsigned blocks_reqd);
  58. static  hdr *add_vmem    (long num_ele, int ele_size, hdr *header);
  59. static  int load_block   (hdr *p, unsigned req_block);
  60. static  int block_io     (int doread, unsigned block, char *buf);
  61.  
  62. PUBLIC int vopen() {
  63. /* Open the virtual-memory system: Create the virtual-memory file and open
  64.  * it for read and write in unbuffered mode. Return true on success, false
  65.  * on failure (errno is set to an appropriate value in this case). The
  66.  * file is called "$$$$vmem.tmp", and it will be put into the directory
  67.  * specified in the TMP environment if this environment is present. E2BIG
  68.  * is used if the path in the TMP environment is too long. */
  69.     char *env;
  70.     int  len;
  71.     if ( !(env = getenv( "TMP" )) )     /* Assemble file name */
  72.         strcpy( Vname, TNAME );         /* No TMP environment */
  73.     else {
  74. /* If a TMP environment exists, use it as a prefix in the file name, 
  75.  * adding a trailing / if necessary. */
  76.         if ((len = strlen( env )) > sizeof(Vname) - 16) {
  77.             errno = E2BIG;
  78.             return 0;
  79.         }
  80.         sprintf( Vname,
  81.             ( len>=2 && env[len-2]!='/' && env[len-2]!='\\' ) ?
  82.                                 "%s/%s" : "%s%s", env, TNAME );
  83.     }
  84. /* Open the file, truncating to zero length if it exists. This is done
  85.  * with creat rather than open to avoid portability problems between
  86.  * Microsoft C and Zortech. The file is opened only for writing, however,
  87.  * so the file has to be closed and reopened for reading and writing. */
  88.     if ( (Vfd = creat(Vname, S_IREAD | S_IWRITE)) == -1 )
  89.         return 0;
  90.     close( Vfd );
  91.     if ( (Vfd = open(Vname, O_RDWR | O_BINARY )) == -1 )
  92.         return 0;
  93.     return 1;
  94. }
  95.  
  96. PUBLIC int vclose() {
  97. /* Close the virtual-memory system and delete vmem file. Return 1 on
  98.  * success, 0 on failure (and errno is set to something reasonable) EBADF
  99.  *  is used if no previous vopen() has been issued. */
  100.     hdr *p, *newp;
  101.  
  102.     if ( Vfd == -1 ) {                   /* the file isn't open */
  103.         errno = EBADF;
  104.         return 0;
  105.     }
  106.     else {
  107.         if ( close( Vfd ) == -1 )        /* close & delete file */
  108.             return 0;
  109.         Vfd = -1;
  110.  
  111.         ND( if ( unlink( Vname ) == -1 )  )
  112.         ND(     return 0;                )
  113.  
  114.         if ( Freelist ) {                /* Empty the free list */
  115.             p = Freelist;
  116.             do {
  117.                 newp = p->next.h;
  118.                 free( p );
  119.             } while ( (p = newp) != Freelist );
  120.             Freelist = NULL;
  121.         }
  122.     }
  123.     return 1;
  124. }
  125.  
  126. PUBLIC hdr *vmalloc( long num_ele, unsigned ele_size ) {
  127. /* Allocate a virtual array, having num_ele, each of ele_size bytes.
  128.  * Return a pointer to use in subsequent operations. The size of the
  129.  * internal buffer used to access elements is controlled by vopen().
  130.  * Return NULL if no virtual memory is available or there is a seek error.
  131.  * Errno will have an appropriate value in it in this case. */
  132.  
  133.     hdr  *prev, *cur, *new, *eof_block ;
  134.     unsigned ele_per_block;     /* elements per block        */
  135.     unsigned blocks_reqd;       /* number of blocks required */
  136.  
  137.     D( printf("Entering vmalloc(%ld,%u). ", num_ele, ele_size); )
  138.     D( pfreelist();                                             )
  139.  
  140.     ele_per_block = BLK_SIZE / ele_size ;
  141.     blocks_reqd = num_ele/ele_per_block + (num_ele % ele_per_block != 0);
  142.  
  143.     if ( Freelist ) {    /* If there is a freelist */
  144.         prev      = Freelist;
  145.         cur       = Freelist->next.h;
  146.         eof_block = NULL;
  147.  
  148.         while ( 1 ) {
  149.             do {
  150.                 if ( cur->offset + cur->nblocks == Filesize )
  151.                     eof_block = cur;    /* last block in file */
  152.  
  153.                 if ( cur->nblocks >= blocks_reqd ) {  
  154.                     Freelist = prev;                 /* it's big enough */
  155.                     if ( cur->nblocks > blocks_reqd ) {
  156.                         cur->nblocks -= blocks_reqd;
  157.                         if ( new = new_hdr( blocks_reqd,
  158.                                     cur->offset + cur->nblocks) )
  159.                             new = add_vmem( num_ele, ele_size, new );
  160.                         goto end;
  161.                     }
  162.                     else {                       /* block is exact size */
  163.                         if ( cur->next.h == cur ) /* no successor */
  164.                             Freelist = NULL;
  165.                         else
  166.                             prev->next.h = cur->next.h;
  167.  
  168.                         new = add_vmem( num_ele, ele_size, cur );
  169.                         goto end;
  170.                     }
  171.                 }
  172.                 prev = cur;         /* go to next freelist element */
  173.                 cur  = cur->next.h;
  174.  
  175.             } while ( prev != Freelist );
  176. /* If we get here, no block in the freelist was large enough. If a block in
  177.  * the free list was at the end of the file, expand it. */
  178.             if ( !eof_block )
  179.                 break;
  180.             else if ( !enlarge(blocks_reqd - eof_block->nblocks) ) {
  181.                 new = NULL;
  182.                 goto end;
  183.             }
  184.             else
  185.                 eof_block->nblocks = blocks_reqd;
  186.  
  187. /* Loop back up. The do/while will catch the newly-expanded object. */
  188.         }               /* end   while ( 1 )     */
  189.     }                   /* end   if ( Freelist ) */
  190.  
  191. /* If we get here, either there was no freelist, or no block big enough in
  192.  * the freelist and we couldn't expand the last block. Make a new block. */
  193.     if ( !(new = new_hdr(blocks_reqd, Filesize)) )
  194.         goto end;
  195.  
  196.     if ( !enlarge( blocks_reqd ) )  {    /* changes Filesize */
  197.         free( new );
  198.         new = NULL;
  199.     }
  200.  
  201.     new = add_vmem( num_ele, ele_size, new );
  202. end:
  203.     D( printf("Leaving vmalloc(%ld,%u). Return:\n", num_ele, ele_size); )
  204.     D( pheader(new);    )
  205.     D( pfreelist();     )
  206.     D( printf("-----------------------------------------\n"); )
  207.     return new;
  208. }
  209.  
  210. PRIVATE hdr *new_hdr( unsigned nblocks, unsigned offset ) {
  211.     hdr *new;
  212.  
  213.     if ( !(new = (hdr *) malloc(sizeof(hdr))) ) {
  214.         errno = ENOMEM;
  215.         return NULL;
  216.     }
  217.     new->nblocks = nblocks;
  218.     new->offset  = offset ;
  219.     return new;
  220. }
  221.  
  222. PRIVATE unsigned enlarge( unsigned blocks_reqd ) {
  223. /* Make the file blocks_reqd bytes larger by seeking that many bytes past
  224.  * end of file. Adjust the global Filesize to indicate the real file size.
  225.  * Return new filesize (in blocks) or 0 if the file couldn't be expanded.
  226.  * Note that the second argument to lseek is an offset. Consequently, it's
  227.  * one less than the count, thus the -1 in the assignment to position. The
  228.  * 1 must be added back in the return statement, however, to make the count
  229.  * work. The write() call both physically expands the file and advances the
  230.  * file pointer one notch. This isn't necessary under UNIX, but MS-DOS
  231.  * needs it. */
  232.     unsigned size_in_blocks;
  233.     long real_size;
  234.     long position ;
  235.  
  236.     position = (long)blocks_reqd * BLK_SIZE - 1;
  237.  
  238.     if ( (real_size = lseek(Vfd, position, SEEK_END)) == -1) {
  239.         errno = ENOMEM;
  240.         return 0L;
  241.     }
  242.  
  243.     if ( write( Vfd, "", 1 ) == -1 )
  244.         return 0L;
  245.  
  246.     ++real_size;
  247.     return( (real_size/BLK_SIZE > (unsigned)~0) ? 0 :
  248.                 (Filesize = (unsigned)(real_size / BLK_SIZE)) );
  249. }      
  250.  
  251. PRIVATE hdr *add_vmem( long num_ele, int ele_size, hdr *header ) {
  252. /* Create a new vmem structure and attach it to the header. Return header
  253.  * argument or NULL if there was a problem. */
  254.     vmem *p;
  255.  
  256.     if ( !(p = (vmem *)malloc( sizeof(vmem))) ) {        /* get the vmem */
  257.         errno = ENOMEM;
  258.         return NULL;
  259.     }
  260.     else if ( !(p->buf = (char *)malloc(BLK_SIZE)) ) {   /* & swap buf. */
  261.         errno = ENOMEM;
  262.         return NULL;
  263.     }
  264.     else {
  265.         header->next.v = p;
  266.         p->signature   = SIGNATURE;
  267.         p->dirty       = 0;
  268.         p->ele_size    = ele_size;
  269.         p->ele_per_blk = BLK_SIZE / ele_size;
  270.         p->num_ele     = num_ele;
  271.         p->cblock      = 0 ;
  272.         return header;
  273.     }
  274. }
  275.  
  276. PUBLIC int vfree( hdr *p ) {
  277. /* Free virtual array pointed to by p. Return true on success, false if the
  278.  * input pointer was invalid (if the first element of the structure wasn't
  279.  * the SIGNATURE). Errno is set to EBADF in this case. */
  280.     int rval = 1;
  281.     hdr *cur, *h;
  282.     vmem *v = p->next.v;
  283.  
  284.     D( printf("Entering vfree(0x%x). ", p ); )
  285.     D( pfreelist();                          )
  286.  
  287.     if ( v->signature == SIGNATURE )
  288.         v->signature = 0;
  289.     else {
  290.         errno = EBADF;
  291.         rval  = 0;
  292.         goto end;
  293.     }
  294.  
  295.     free( v->buf );     /* discard the swap buffer    */
  296.     free( v );          /* discard the vmem component */
  297.  
  298.     if ( !Freelist ) {   /* Free list is empty. Create a new one. */
  299.         Freelist = p->next.h = p;
  300.         goto end;                       /* return default value */
  301.     }
  302.  
  303. /* Find out where the newly freed node goes: The list is a circular linked
  304.  * list arranged in ascending order of offset. Since it's circular, there
  305.  * will be one place where cur->offset > cur->next.h->offset (see 1,
  306.  * below). We have to test for the normal situation where the new node
  307.  * comes between the current node and its successor. The rest of the
  308.  * following if statement tests for the corner situations when the new
  309.  * node's offset is either larger (at 2) or smaller (at 3) than anything
  310.  * currently in the list. */
  311.     for ( cur = Freelist ; 1 ; cur = cur->next.h ) {
  312.        if (  ( cur->offset < p->offset &&
  313.                p->offset < cur->next.h->offset
  314.              ) ||
  315.              ( cur->offset >= cur->next.h->offset &&   /* 1 */
  316.                  ( cur->offset < p->offset ||           /* 2 */
  317.                    p->offset < cur->next.h->offset     /* 3 */
  318.                  )
  319.              )
  320.          )
  321.                break;
  322.     }
  323. /* Now link the node into the list, coalescing if necessary. First
  324.  * handle degraded case of a free list with only one element. */
  325.     if ( cur == cur->next.h ) {    /* only block in chain */
  326.         if ( p->offset + p->nblocks == cur->offset ) {
  327.             cur->offset   = p->offset;
  328.             cur->nblocks += p->nblocks;
  329.             free( p );
  330.             goto end;
  331.         }
  332.         else if ( cur->offset + cur->nblocks == p->offset ) {
  333.             cur->nblocks += p->nblocks;
  334.             free( p );
  335.             goto end;
  336.         }
  337.     }
  338.  
  339. /* Now handle normal case. Link or coalesce to the right first, 
  340.  * then to the left. */
  341.     if ( p->offset + p->nblocks == cur->next.h->offset ) {
  342.         /* The blocks are adjacent. Coalesce and free the extra header. */
  343.         p->nblocks += cur->next.h->nblocks;
  344.         p->next.h   = cur->next.h->next.h;
  345.         free( cur->next.h );
  346.     }
  347.     else
  348.         p->next.h = cur->next.h;
  349.     if ( cur->offset + cur->nblocks == p->offset ) {
  350.         cur->nblocks += p->nblocks;      /* Adjacent */
  351.         cur->next.h   = p->next.h;
  352.         free( p );
  353.     }
  354.     else
  355.         cur->next.h = p;
  356.  
  357. end:
  358.     D( printf("Leaving vfree(0x%x). Returning %d. ", p, rval ); )
  359.     D( pfreelist();                                             )
  360.     D( printf("-------------------------------------------\n"); )
  361.     return rval;
  362. }
  363.  
  364. PUBLIC void *vread ( hdr *p, long index ) {
  365. /* Returns pointer to array element at indicated offset from the virtual 
  366.  * array pointed to by p. Returns NULL if offset is out of bounds or the
  367.  * block couldn't be loaded (errno is set too). */
  368.     unsigned block_num;       /* block in which index is found */
  369.     vmem     *v = p->next.v;  /* vmem component of *p          */
  370.  
  371.     if ( index < 0  ||  index > v->num_ele ) {
  372.         errno = ERANGE;       /* index is out of range */
  373.         return 0;
  374.     }
  375.     if ( v->signature != SIGNATURE || Vfd == -1 ) {
  376.         errno = EBADF ;       /* signature doesn't match */
  377.         return 0;
  378.     }
  379.  
  380.     block_num = index / v->ele_per_blk ;
  381.     if ( !load_block( p, block_num ) )
  382.         return NULL;
  383. /* get the pointer:
  384.  * (1) adjust index so it's relative to the start of the current block
  385.  * (2) Multiply by the element size to get a byte offset.
  386.  * (3) Add to base address of buffer to get pointer. */
  387.     index -= block_num * v->ele_per_blk;        /* (1) */
  388.     index *= v->ele_size;                       /* (2) */
  389.     return( v->buf + index );                   /* (3) */
  390. }
  391.  
  392. PUBLIC void *vwrite( hdr *p, long index, char *this ) {
  393. /* Transfer *this to the virtual array at the indicated index. Return a
  394.  * pointer to the actual memory location for *this or NULL on an i/o
  395.  * failure or a bad "p" argument. */
  396.  
  397.     int  i;
  398.     char *bp;
  399.     void *startp;
  400.     vmem *v = p->next.v ;
  401.  
  402.     if ( startp = bp = vread( p, index ) ) {
  403.         for ( i = v->ele_size; --i >= 0 ;)
  404.             *bp++ = *this++;
  405.         v->dirty = 1;
  406.     }
  407.     return startp;
  408. }
  409.  
  410. PRIVATE int load_block( hdr *p, unsigned req_block ) {
  411. /* Load a block. The base offset is in p->offset and req_block is
  412.  * the additional offset needed to get to the correct block. */
  413.     vmem *v = p->next.v;
  414.     if ( req_block != v->cblock ) {
  415.         if ( v->dirty && ! block_io ( WRITE, 
  416.                                        p->offset + v->cblock, v->buf) )
  417.                 return 0;
  418.         if ( !block_io(READ,  p->offset + req_block, v->buf))
  419.             return 0;
  420.         v->dirty  = 0;
  421.         v->cblock = req_block;
  422.     }
  423.     return 1;
  424. }
  425.  
  426. PRIVATE int block_io( int doread, unsigned block_num, char *buf ) {
  427. /* Read or write a block, depending on the value of doread, into or from
  428.  * buf. block_num is the absolute block number. */
  429.     size_t got;         /* wrote or read this many bytes         */
  430.     long   here;        /* for debugging, make sure we got there */
  431.  
  432.     here = lseek( Vfd, (long)block_num * BLK_SIZE, SEEK_SET);
  433.     if ( here== -1 )
  434.         return 0;
  435.  
  436.     got = doread ? read (Vfd, buf, (size_t) BLK_SIZE)
  437.                  : write(Vfd, buf, (size_t) BLK_SIZE) ;
  438.  
  439.     if ( got == -1 )
  440.         return 0;
  441.  
  442.     /* it's an error if we didn't write the block, it's not an error if we
  443.      * didn't read it, however. We may be trying to read a block at the end
  444.      * of file that hasn't been written to yet-not a problem under UNIX but
  445.      * it is under DOS. */
  446.  
  447.     return( doread ? 1 : (got == BLK_SIZE) );
  448. }
  449.  
  450. PUBLIC long vele  ( hdr *p ) { return p->next.v->num_ele; }
  451. PUBLIC void vdirty( hdr *p ) { p->next.v->dirty = 1;      }
  452. #ifdef DEBUG
  453. pfreelist() {
  454.     hdr *p;
  455.     if ( !(p = Freelist) )
  456.         printf("Freelist is empty.\n");
  457.     else {
  458.         printf("Freelist is:\n");
  459.         do { pheader(p);
  460.         } while ( (p = p->next.h) != Freelist );
  461.     }
  462. }
  463. pheader( hdr *p ) {
  464.     if ( !p )
  465.         printf("NULL");
  466.     else
  467.         printf("hdr   x%x: offset=%u nblocks=%u next=0x%x%s\n",
  468.                             p, p->offset, p->nblocks, p->next.h,
  469.                             p == Freelist ? " <-Freelist" : "" );
  470. }
  471. #endif /* ifdef DEBUG */
  472.  
  473.